'''
二叉树的深度优先遍历
递归的前序中序后序
'''

res = []
def preorder(self, node):

    if node == None:
        return
    else:
        # 根左右
        res.append(node.val)
        self.preorder(node.left)
        self.preorder(node.right)
    # 定义深度优先遍历中的中序遍历



def inorder(self, node):
    if node == None:
        return
    else:
        # 左根右
        self.inorder(node.left)
        print(node.val)
        self.inorder(node.right)
    # 定义深度优先遍历中的后序遍历


def postorder(self, node):
    if node == None:
        return
    else:
        # 左右根
        self.postorder(node.left)
        self.postorder(node.right)
        print(node.val)

# 非递归的深度优先遍历
'''
二叉树的广度优先遍历，层序遍历
'''
# 定义广度优先遍历(层次遍历)方法
def breadth_travel(root):
    res = []
    if not root:
        return
    # 仍然是用队列的方式实现遍历，末端按遍历顺序逐个添加节点，首端逐个弹出先读到的节点
    queue = []
    queue.append(root)
    while queue:
        # 核心在于用队列实现pop(0),也就是先放进队列的就会先被拿出来，于是就是广度优先！
        cur = queue.pop(0)
        res.append(root.val)
        if cur.left:
            queue.append(cur.left)
        if cur.right:
            queue.append(cur.right)
    return res

'''
非递归，深度优先
'''
def postOrder(self, root):
    if root == None:
        return
    stack=[root.val]
    res=[]
    while stack:
        cur = stack.pop()
        res.append(cur)
        if cur.left:
            stack.append(cur.left)
        if cur.right:
            stack.append(cur.right)
    return res
